Міністерство освіти і науки, молоді та спорту України Національний університет “Львівська політехніка” Кафедра ЕОМ Звіт з лабораторної роботи № 4 на тему: " Структура даних ЧЕРГА " з дисципліни: " Програмування. Частина III. Структури даних та алгоритми " Вибір варіанту: № варіанта = [(день народження) + (місяць народження) + (ASCII–код першої літери прізвища – велика латинська літера) ] % 20 + 1 (23 + 8 + 70 ) % 30 + 1 = 2 Львів – 2013 Мета роботи: Вивчення фундаментальної абстрактної структури даних - черги. Набуття практичних навичок побудови черги, дослідження динаміки її вмісту та використання черг для розв'язання прикладних задач. Постановка задачі: 2. Змоделювати чергу, в якій до опису черги додано дві змінні EMPTY та FULL замість функцій empty() та full() відповідно. Переписати основні функції роботи з чергою з врахуванням цих змінних. Показати динаміку вмісту черги. Після обробки всієї заданої вхідної послідовності перевірити, чи є в черзі три однакових елемента, що йдуть підряд. Код програми: #pragma once #include<cassert> #include<stdio.h> #include<tchar.h> #include<iostream> const int M = 100; template<class Item> class queue { private: Item INFO[M]; int count; public: queue( ); void pop( ); void push(const Item& entry); bool empty( ) const { return (count == 0); } Item front( ) const; int size( ) const { return count; } void show(); void muve(); bool full(){return (INFO[M-1] == M-1);}; void wipe_out(); bool same(); }; template<class Item> queue<Item>::queue( ) { count = 0; INFO[0] = 1; INFO[M-1] = 0; } template<class Item> Item queue<Item>::front( ) const { assert(!empty( )); return INFO[1]; } template<class Item> void queue<Item>::pop( ) { muve(); count--; } template<class Item> void queue<Item>::push(const Item& entry) { assert(!(count > M - 1)); ++count; INFO[++INFO[M-1]] = entry; } template<class Item> void queue<Item>::show() { std::cout <<"QUENE: "; for(int i = INFO[0]; i < INFO[M-1]+1; i++){ std::cout << INFO[i] <<" " ; } std::cout << std::endl; } template<class Item> void queue<Item>::muve() { for(int i = INFO[0]; i < INFO[M-1]; i++){ INFO[i] = INFO[i+1]; } --INFO[M-1]; } template<class Item> void queue<Item>::wipe_out() { for (int i=0; i<count; i++) { muve(); } count = 0; } template<class Item> bool queue<Item>::same() { bool b = false; for (int i=0; i<count-1; i++) if (INFO[i]==INFO[i+1]) { b = true; } return b; } using namespace std; int main() { queue<int> q; int v[M], m; int k = 0; cout <<"ENTER VALUE OF QUEUE TO CONTINUE OR TEXT TO EXIT..."<< std::endl; while(cin >> v[k++]) { m = k; } q.show(); for(k = 0; k < m; k++) { if (v[k]==0) { q.wipe_out(); q.show(); } if (v[k]>0) { q.push(v[k]); q.show(); } if (v[k]<0) { q.pop(); q.show(); } } cout <<"\nSIZE: "<< q.size() << endl; cout <<"EMPTY: "<< boolalpha << q.empty() << endl; cout <<"FULL: "<< boolalpha << q.full() << endl; cout <<"FRONT: "<< q.front() << endl; cout <<"THE SAME ELEMENTS IN QUEUE: "<< q.same() << endl; cin.get(); return 0; } Результат виконання програми:
Рис1. Ескіз вікна з результатом виконання програми Висновок: Виконавши дану лабораторну роботу, я навчився будувати та застосовувати абстрактні типи даних типу «Черга». Зрозумів як працює стек та які функції виконує.